package com.leetcode;

/**
 * @Classname Leetcode200
 * @Description TODO
 * @Date 2021-08-14 15:49
 * @Created by darrren
 */
public class Leetcode200 {


    /*
    //solution 1: 深度优先算法
    private int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private int m;
    private int n;

    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;

        int count = 0;
        //两层循环，找到'1'，并且将'1'相邻的'1'都设置成'0'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfsMarking(grid, i, j);
                    //先清除整块区域的'1'再 count++，这样子就不会重复计算
                    count++;
                }
            }
        }

        return count;
    }

    private void dfsMarking(char[][] grid, int i, int j) {
        //1) 判断是否越界
        //2) 判断是否是'1'
        if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == '1') {
            //先将当前位置设置成'0'
            grid[i][j] = '0';
            //遍历上下左右四个方向，寻找'1'
            for (int k = 0; k < directions.length; k++) {
                dfsMarking(grid, i + directions[k][0], j + directions[k][1]);
            }
        }
    }
*/
    class UnionFind {
        int count;
        //parent表示每个圈的父节点
        int[] parent;
        //rank 表示深度.两个圈合并，深度越小越好
        int[] rank;

        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length;
            int n = grid[0].length;
            parent = new int[m * n];
            rank = new int[m * n];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') {
                        // 初始化: 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
                        //二维数组转换成一维数组
                        parent[i * n + j] = i * n + j;
                        //每一个'1'自成一个圈
                        ++count;
                    }
                    rank[i * n + j] = 0;
                }
            }
        }

        public int find(int i) {
            //如果parent不是自己
            if (parent[i] != i) {
                parent[i] = find(parent[i]);
            }
            return parent[i];
        }

        public void union(int x, int y) {
            int rootx = find(x);
            int rooty = find(y);
            if (rootx != rooty) {
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else {
                    parent[rooty] = rootx;
                    rank[rootx] += 1;
                }
                //合并之后，岛屿的数量减一
                --count;
            }
        }

        public int getCount() {
            return count;
        }
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        UnionFind uf = new UnionFind(grid);
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    //清除标志位，防止重复计算
                    grid[r][c] = '0';
                    //上下左右四个方向分别尝试
                    for (int k = 0; k < directions.length; k++) {
                        int newR = r + directions[k][0];
                        int newC = c + directions[k][1];
                        if (newR >= 0 && newR < nr && newC >= 0 && newC < nc && grid[newR][newC] == '1') {
                            uf.union(r * nc + c, newR * nc + newC);
                        }
                    }
                    /*
                    if (r - 1 >= 0 && grid[r - 1][c] == '1') {
                        uf.union(r * nc + c, (r - 1) * nc + c);
                    }
                    if (r + 1 < nr && grid[r + 1][c] == '1') {
                        uf.union(r * nc + c, (r + 1) * nc + c);
                    }
                    if (c - 1 >= 0 && grid[r][c - 1] == '1') {
                        uf.union(r * nc + c, r * nc + c - 1);
                    }
                    if (c + 1 < nc && grid[r][c + 1] == '1') {
                        uf.union(r * nc + c, r * nc + c + 1);
                    }
                    */
                }
            }
        }

        return uf.getCount();
    }


    public static void main(String[] args) {
        char[][] grid = new char[][]{
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };

        Leetcode200 leetcode = new Leetcode200();
        System.out.println(leetcode.numIslands(grid));

    }
}
